Computer file systems, which organize stored data into files and directories, often utilize metadata to maintain information about the files and directories. For example, UNIX-style file systems (e.g., UFS, VXFS, EXT, etc.) maintain a respective inode data structure for each file and directory in the system. An inode corresponding to a file or directory typically stores various metadata about that file or directory, such as a unique identifier, a storage location, access rights, owner identifier, creation/access records, and/or other fields. The term file metadata is used herein to refer to such metadata, whether it corresponds to a file, to a directory, and/or to any other file system construct. The term inode is used herein to refer generically to any data structure that stores file metadata, without restriction to any particular internal structure.
Inodes may be stored in persistent storage (e.g., disk) along with file data. To access a file, an operating system (OS) may first locate the file's inode on disk, read the file metadata into memory, and then use the metadata to locate and read the file. However, reading an inode from off-memory storage (e.g., disk) may be relatively slow and therefore, applications that open many files may suffer performance degradation.
To speed access to file metadata, some file systems (e.g., VXFS) maintain an in-memory file metadata cache that stores recently accessed file metadata, such as in an in-memory inode data structure. When the OS later attempts to access the same file, the OS may read the corresponding metadata from the in-memory cache rather than perform a slow access to off-memory storage. Such a cache may be referred to herein as a file metadata cache or inode cache.
Since memory is a limited resource, the inode cache cannot grow indefinitely to store metadata from every file system element that the OS accesses. Instead, the OS may initialize a set of inodes in the inode cache and use those inodes to store accessed file metadata. If the OS needs to store new file metadata into a full cache, the OS may choose a cached inode to “evict” and replace the metadata in the determined inode with the new file metadata. This process may be referred to herein as repurposing or replacing the inode. The OS may choose the particular inode to repurpose according to various replacement policies.
The effectiveness of an inode cache may depend substantially on the effectiveness of its replacement policy. Traditional inode caches utilize a least-recently used (LRU) replacement policy, whereby the least-recently accessed inode in cache is first to be repurposed. Some techniques, such as those used in set-associative inode caches, may vary the LRU technique somewhat by mapping the inserting metadata into a given set of inodes and repurposing the least-recently used inode in that set. However, such set-associative techniques maintain the same basic LRU character as fully associative techniques that do not utilize sets.
Although LRU replacement policies may perform reasonably in many situations, the policy is sometimes suboptimal. An inode cache operating according to a suboptimal replacement policy may confer only limited benefit. Furthermore, because systems incur overhead when repurposing inodes, an inode cache with a poor replacement policy may even harm overall system performance in degenerate cases.